#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/*
完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
CBTInserter.get_root() 将返回树的根节点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/NaqhDT
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class CBTInserter
{
private:
    TreeNode *root;
    queue<TreeNode *> q;

public:
    CBTInserter(TreeNode *root)
    {
        this->root = root;
        q.push(root);
        while (q.front()->left && q.front()->right)
        {
            q.push(q.front()->left);
            q.push(q.front()->right);
            q.pop();
        }
        //最后还有左子树的话
        if (q.front()->left)
            q.push(q.front()->left);
    }

    int insert(int v)
    {
        int result = q.front()->val;
        if (!q.front()->left)
        {
            q.front()->left = new TreeNode(v);
            q.push(q.front()->left);
        }
        else
        {
            q.front()->right = new TreeNode(v);
            q.push(q.front()->right);
            q.pop();
        }
        return result;
    }

    TreeNode *get_root()
    {
        return root;
    }
};